package cn.bouncyslime.algorithms.dynamicPlan.triangle;
// 数字三角形问题，采用备忘录方法
/*
 * 左右相等选择左
 */
/*
 * 备忘录方法和动态规划方法一样，都需要记录每一次运算所得到的子问题的值，在次问题中，将子问题的解存放到二位数组中
 * 不同的是，备忘录方法采取的是自顶向下递归，动态规划方法采用的是自底向上的方法，两者的算法结构有很大的不同。
 */
public class MaxSumTri {
	//创建三个类变量的二位数组，分别代表，初始的二维矩阵，路径矩阵，各个位置的最大加和矩阵，其中后两个矩阵初始化为0
	static int[][] initMatrix = {{9,0,0,0,0},{12,15,0,0,0},{10,6,8,0,0},{2,18,9,5,0},{19,7,10,4,16}};
	static int[][] pathMatrix = new int[5][5];
	static int[][] maxSumMatrix = new int[5][5];
	
	//程序的主体，用来自顶向下递归地求每一个位置的最大加和。
	public int maxSum(int tri, int trj) {
		//这个是递归程序的边界条件，小于4时继续向下迭代
		if(tri<initMatrix.length-1) {
			int flag = 0, flag2 = 0;
			if(maxSumMatrix[tri][trj] == 0){
				//解决子问题，求出子问题的最优解，之后记录并返回
				flag = initMatrix[tri][trj] + maxSum(tri+1, trj);
				flag2 = initMatrix[tri][trj] + maxSum(tri+1, trj+1);
				if(flag >= flag2){
					maxSumMatrix[tri][trj] = flag;
				}else{
					maxSumMatrix[tri][trj] = flag2;
				}
				return maxSumMatrix[tri][trj];
			}
			return maxSumMatrix[tri][trj];
		}
		//等于4时，因为已经到达了矩阵的最底层，所以直接返回的是该位置的值，因为已经没有再向下的数
		maxSumMatrix[tri][trj] = initMatrix[tri][trj];
		return initMatrix[tri][trj];
	}
	//遍历最大加和矩阵，判断出每一行的最大的数，就是从下向上在这里经过的这个位置
	public void getPath(int[][] array) {
		pathMatrix[0][0] = 1;
		int flag3 = 0;
		for(int i=1; i<array.length; i++) {
			if(i==4) {
				if(maxSumMatrix[i][flag3]>=maxSumMatrix[i][flag3+1]) {
					pathMatrix[i][flag3] = 1;
				}else {
					pathMatrix[i][flag3+1] = 1;
				}
				break;
			}
			int flag = array[i][0];
			int flag2 = 0;
			for(int j=0; j<i; j++) {
				if(array[i][j+1] >= flag) {
					flag = array[i][j+1];
					flag2 = j+1;
					flag3 = flag2;
				}
			}
			pathMatrix[i][flag2] = 1;
		}
	}
	// 初始化矩阵
	public void initArray(int[][] array, int num) {
		for(int i=0; i<array.length; i++) {
			for(int j=0; j<array[i].length; j++) {
				array[i][j] = num;
			}
		}
	}
	// 输出矩阵
	public void printArray(int[][] array) {
		for(int i=0; i<array.length; i++) {
			for(int j=0; j<array[i].length; j++) {
				System.out.printf("%4d", array[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		MaxSumTri m = new MaxSumTri();
		m.initArray(pathMatrix, 0);	
		m.initArray(maxSumMatrix, 0);
		System.out.println("初始矩阵是：");
		m.printArray(initMatrix);
		int result = m.maxSum(0, 0);
		System.out.println("最后的结果是："+result);
		System.out.println("加和矩阵是：");
		m.printArray(maxSumMatrix);
		System.out.println("路径矩阵是：");
		m.getPath(maxSumMatrix);
		m.printArray(pathMatrix);
	}
	
}
